The present invention relates to methods and systems for maintaining data structures that are useful for facilitating a wake-up of a flash memory system.
U.S. Pat. No. 6,510,488 of Lasser entitled “Method For Fast Wake-Up of a Flash Memory System” (hereinafter “Lasser '488”) discloses a method and system for allowing a flash memory system to achieve a fast wake-up time after powering the flash memory system up even if the flash system software relies on management tables whose generation from scratch is time-consuming. This fast wake-up time is achieved without sacrificing data integrity. The aforementioned patent of Lasser '488 is incorporated by reference for all purposes as if fully set forth herein.
As explained in Lasser '488, using a flash memory device for computer data storage traditionally requires a software translation layer that sits between the host computer's operating system and the device low-level access routines. This is so because the flash technology has some usage limitations, which make the flash memory impossible to access in a simple random-access linear method. One such limitation is the inability to randomly overwrite any desired flash memory location. Specifically, the writing of new content into a flash memory location may require first erasing the whole block containing that location (preserving the contents of any other locations still needed), and only then writing the new content.
The translation layer presents to the hosting operating system a virtual view of a random-access addressable array of independent data sectors, while hiding and handling the details of mapping those virtual addresses into their real locations in the flash media. This translation mechanism is far from trivial, and an example of such a flash memory translation layer is disclosed in Amir Ban's U.S. Pat. No. 5,937,425, which is incorporated as if fully set forth herein. Ban discloses a method for implementing a mapping mechanism between virtual and physical flash addresses. Another example of such as system is detailed in U.S. Pat. No. 6,678,785, which is also incorporated by reference for all purposes as if fully set forth herein.
The translation process relies on internal translation tables that provide the flash system software with the information required for converting the host computer data access requests to the actual flash access requests. These translation tables are constructed by the flash memory system software during system wake-up (or at later time, if so requested by the hosting software), based on control information stored within the flash device. Even though it is theoretically possible not to construct such tables and instead to use only the raw control data from the flash memory, this is practically unusable as the response time to an access request would be too slow. This is so because accessing data on flash is much slower than accessing data in RAM memory, and also because the RAM memory tables are usually optimized for efficiency in the type of operations required during runtime, while the flash-stored control data is not.
For example, a flash physical unit might contain the number of the virtual unit mapped to it. During program runtime we may frequently need to translate a virtual unit number into its physical counterpart. If we have to rely only on flash-stored control data, we may need to scan the units until we find the unit with the specified virtual unit number, a very long process by the standards of a simple media access. However, by scanning the flash device once on system wake-up and constructing a table mapping each virtual unit number into a corresponding physical unit number, we are able to later do such mappings very efficiently.
The problem is that scanning the flash data storage device on system wake-up might take a long time, especially for high capacity devices. This is especially annoying for systems and devices in which a user expects immediate turn-on (i.e. cellular phones, PDAs, etc.). Simply storing the tables in the flash memory may work for read-only devices, such as flash devices storing only computer executable code that is not changeable by the user. However, merely storing the tables in flash memory will not succeed when using devices used to store data which might be changing frequently (such as text files or spreadsheets in a PDA). This is so because when continuously writing to the device and changing the device's contents, the contents of the translation tables also change. It is not practical to update the copy of the tables in the flash memory each time the tables change in RAM, because the incurred overhead will slow the system considerably. Consequently, a difference will be accumulated between the tables stored in flash memory and the “correct” ones in RAM. Now if the user switches the power off and then turns the power back on, without updating the tables, the software will read incorrect translation tables from flash memory, and the results might be data loss when writing new data.
According to some embodiments disclosed in Lasser '488, this problem is solved by storing translation tables in the flash memory and adding some means for the software to invalidate the translation tables in a way that is detectable whenever reading them. Possible implementations (but not the only implementations) include adding a checksum value that makes the sum of all entries equal some fixed known value, or adding a validity flag to the stored tables. Additionally, one should ask the application software to call a specific function in the translation layer before shutting the system down.
In these ways the flash memory device is able to initiate fast wake-ups when the system undergoes an orderly shut down, and reverts to regular wake-ups when the system undergoes an un-orderly shut down.
While this solution is useful for many cases, there are situations where this solution may not be adequate. A first example where the solution may not be adequate is when sudden power failures are frequent and it is expected that many (or even most) of the power-up events will encounter invalid stored tables and will result in regular wake-ups that are slow.
A second example where the solution may not be adequate is where the operating system of the appliance hosting the flash memory system does not provide the software application with a service for orderly device dismounting or shutting down. While complex operating systems like Linux do provide such service, there are many simpler and smaller operating systems that are designed for starting up the storage system upon power-on and never shut the operating system down. In such cases the methods of Lasser '488 will result in every power-up of the system doing a regular wake-up of the flash management system, gaining nothing from those methods.
A third example where the solution may not be adequate is where there is a strict limit on the length of the time interval between powering the system up and having the system ready for operation. So even if power failures are rare and almost all power-up cases result in a fast wake-up of the flash management system, it is still unacceptable that a power failure will cause a later regular power-up sequence, regardless of how rarely this occurs.
Because of the above inadequacies of Lasser '488, U.S. patent application Ser. No. 11/382,056 to Lasser (hereinafter “Lasser '056”) discloses another solution to the problem of a fast wake-up of flash management systems. The aforementioned application of Lasser '056 is incorporated by reference for all purposes as if fully set forth herein.
Lasser '056 discloses a technique whereby one or more flash management tables are updated and saved in flash memory after some but not after all events of the flash memory system. When waking up, if it turns out that a given flash management table stored in the flash memory contains out-of-date information, it is still possible to use the stored table(s) to facilitate system wake-up, and there is no requirement to invalidate the out-of-date table. Instead of invalidating this table, the out-of-date flash management table saved in flash memory before shut down and/or power loss may, when waking up, be used to re-construct the “proper” table (i.e. reflecting a current state of the system)
This is carried out by concurrently maintaining in flash memory an events log. When waking up, data stored in the events log are used to update the flash memory table and thereby maintain data integrity even if there was not an orderly exit before loss of power or shut-down. In most cases, the deriving of an “up-to-date” from an “out-of-date” table stored in flash memory using an events log is faster than the constructing of an up-to-date table by scanning the flash storage device.
A drawback of Lasser '056 is that it requires maintaining an events log in the flash memory. While in some flash management systems this is not a real drawback because an events log is already maintained for other reasons, there are many flash management systems in which an events log is not otherwise required, making the use of the methods of Lasser '056 costly in write performance.
There is thus a widely recognized need for, and it would be highly advantageous to have, a method and system that can provide a method for fast wake-up of a flash memory system, without compromising the integrity of the flash data structures and without sacrificing performance.